package 代码随想录.贪心算法.合并区间;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

//合并区间，去哪儿旅行手撕碰到
public class LeetCode56 {
    public static int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        //按照左边界排序
        Arrays.sort(intervals, (x1, x2) -> Integer.compare(x1[0], x2[0]));
        //第一个区间可以先放进去，如果后面重叠，在res上面直接合并
        res.add(intervals[0]);
        //其实我们res中的最后一个区间的右边界相当于当前的最大右边界了
        //如果后面遍历的区间左端点小于整个最大右边界，说明区间重叠，需要合并
        //否则直接加入res就行
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= res.getLast()[1]) {  //区间重叠
                int start = res.getLast()[0];
                int end = Math.max(intervals[i][1], res.getLast()[1]);
                //删除res最后一个结点
                res.removeLast();
                //将合并后的区间加入res
                res.add(new int[]{start, end});
            } else {
                //没发生重叠直接加入就行
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }

    public static void main(String[] args) {
        int[][] intervals = {
                {1, 3},
                {2, 6},
                {8, 10},
                {15, 18}
        };
        int[][] merge = merge(intervals);
        Arrays.stream(merge).forEach(x -> {
            System.out.println(Arrays.toString(x));
        });
    }
}
